The present invention generally relates to technology of evaluating performance of an integrated circuit such as CMOS (Complementary Metal-Oxide Semiconductor) and LSI (Large Scale Integration) in its design. More particularly, the present invention relates to technology of calculation of delay distribution, and removal and extraction of false paths.
In the VLSI (Very Large Scale Integration) design in deep sub-micron era, it is necessary to take variation in manufacturing process into account in advance so that circuits with required performance are produced with high yield. Like the technology such as OPC (Optical Proximity Correction), variation control by mask shape correction has become possible, and is increasingly required in practical applications. Therefore, the future VLSI physical design requires technology of designing a highly integrated, high performance circuit by setting proper design margins for each transistor in view of the manufacturing variation.
A method for estimating variation in circuit performance such as critical path delay resulting from manufacturing variation is essential to such design technology. Since the distribution of critical path delay is independent of input, statistical static timing analysis can be used as a method for estimating variation in critical path delay.
One method for statistical static timing analysis is to estimate the maximum delay on the assumption that variations in signal transmission time do not have a correlation (disclosed in M. Hashimoto and H. Onodera, xe2x80x9cA performance optimization method by gate resizing based on statistical static timing analysis,xe2x80x9d Proc. Workshop on Synthesis And System Integration of Mixed Technology (SASIMI 2000), pp. 77-82, 2000).
On the other hand, one method for static timing analysis of a combinational circuit formed from CMOS logic gates is as follows: a given circuit 100 as shown in FIG. 9 is represented by an acyclic graph G=(V, E) 200 as shown in FIG. 10, and in this graph G 200, the maximum delay required to propagate a value xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d is obtained for each output terminal v.
In FIG. 10, each dashed ellipse 210 corresponds to a primary input terminal and a primary output terminal of the circuit and input/output terminals of a logic gate. A white circle 211 and a black circle 212 in an ellipse 210 corresponding to a terminal v are 0-vertex v0 and 1-vertex v0 of v, respectively, where v0 and v1 indicate that the corresponding terminal v has signal values xe2x80x9c0xe2x80x9d and xe2x80x9c1xe2x80x9d, respectively.
Moreover, S indicates a set of sources into which no edge comes, and T is a set of sinks from which no edge goes out. The sources correspond to the primary input terminals, and the sinks correspond to the primary output terminals. Each directed path from a source to a sink in the graph G is referred to as a path. Although the direction of each edge is not shown in FIG. 10, every edge is a directed edge going out from a left vertex and coming into a right vertex.
In FIG. 10, each box 221, 222, 223 represents a logic gate in the circuit 100. The left vertices in each box correspond to the input terminals of the corresponding logic gate, and the right vertices in each box correspond to the output terminal of the corresponding logic gate. Each edge in the box goes out from a vertex representing input of the corresponding logic gate into a vertex representing output thereof. In the case where the box represents a NAND gate or a NOR gate, each edge in the box corresponds to PMOS or nMOS in the corresponding gate. The way to generate the edges is determined according to the type of logic gate. Each edge connecting vertices in different boxes corresponds to an interconnect, and edge eO going out from 0-vertex of a terminal reaches 0-vertex of another terminal, and edge el going out from 1-vertex of a terminal reaches 1-vertex of another terminal.
The true maximum delay required to propagate a value xe2x80x9c0xe2x80x9d to a terminal v is herein denoted by d0(v), and the true maximum delay required to propagate a value xe2x80x9c1xe2x80x9d is herein denoted by d(1). Herein, d0(v), d1(v) for each terminal v of the circuit are represented by the longest path lengths d(v0), d(v1) from a sink to v0, v1 on the graph G, respectively. Therefore, the delay required to transmit a signal value from a terminal v to a terminal w is assigned to each edge e=(v, w) as a weight t(e).
Simulation using such an acyclic graph made it possible to conduct timing analysis of a logic circuit by a relatively simple process.
In delay calculation of a signal z in the circuit 100 as shown in FIG. 9, however, if the delays of signals x and y heavily depend on the delay of a signal b, there is a significant correlation between the delays of the signals x and y. If there is variation in interconnect delay, there is also a correlation between the signal transmission delays of fanout of the signal b. Accordingly, the statistical analysis that does not take correlation into account is likely to be inaccurate.
When delay distribution estimation has poor accuracy, it must be ensured that an integrated circuit will operate in a normal condition even under a plurality of worst conditions which are not likely to occur simultaneously in actual situations, resulting in design including excessive margins. This unnecessarily increases the area and costs such as power consumption in the designed integrated circuit.
The conventional methods have additional problems.
The conventional methods include paths that cannot be simulated actually (false paths). This results in excessively increased calculation time, degraded accuracy in delay estimation, and the like.
The false paths can be divided into two types: logical false paths and functional false paths. A logical false path is a path that will not be activated actually since there is no input for logically propagating a signal to that path. A functional false path is a path that will not be activated since there is an input for activating that path but such an input will not be produced actually. For example, in FIG. 11, among the paths passing through two AND gates G1, G6 controlled by complementary signals z,/z, such a path that the input x of the AND gate Gl other than the input z becomes xe2x80x9c1xe2x80x9d and the output y of the AND gate G6 becomes xe2x80x9c1xe2x80x9d corresponds to a logical false path. For example, when operation by a series of operating units (X, M, Y) and a series of operating units (A, M, B) is required, the use of a common multiplier M would result in a series of operating units (A, M, Y) or (X, M, B). However, if the specification does not allow simultaneous operation of the operating units, these series of operating units correspond to functional false paths.
It is practically impossible for human beings to find logical false paths in view of the large circuit scale. Therefore, an automatic finding method using a computer is essential.
It is an object of the present invention to provide a method for calculating delay distribution of an integrated circuit, which is capable of calculating delay distribution more accurately according to an actual circuit.
It is another object of the present invention to provide an integrated circuit evaluation method having improved evaluation accuracy while avoiding effects of a false path. The present invention also proposes a method for extracting a false path from an integrated circuit to be designed.
More specifically, according to the present invention, in a method for calculating delay distribution in an integrated circuit to be designed, the delay distribution is calculated based on correlation information indicating a correlation of performance between interconnects or elements that are included in the integrated circuit.
According to the present invention, the delay distribution of the integrated circuit is calculated based on correlation information indicating a correlation of performance between the interconnects and elements that are included in the integrated circuit. This enables the delay distribution of the integrated circuit to be calculated with improved accuracy.
Preferably, the delay distribution calculation method according to the present invention includes the steps of: generating a graph representing the integrated circuit based on circuit information indicating connection between elements in the integrated circuit; and calculating delay distribution of each vertex in the graph by using performance distribution information and the correlation information. The performance distribution information indicates performance distribution of the interconnects and the elements that are included in the integrated circuit.
Preferably, the calculation step includes a first step of selecting from the graph a vertex that does not belong to a set of vertices whose delay distribution has been calculated as a vertex for calculation, and a second step of calculating for the vertex selected in the first step the delay distribution and a correlation of performance with each vertex belonging to the set, based on the performance distribution information and the correlation information, and the first and second steps are repeatedly conducted while adding to the set the vertex whose delay distribution has been calculated.
Preferably, the delay distribution calculation method according to the present invention includes the step of producing the correlation information based on layout of the integrated circuit by using correlation characteristics information. The correlation characteristics information indicates a relation between the correlation of performance between the interconnects or the elements and layout characteristics.
According to the present invention, a method for evaluating an integrated circuit to be designed includes: a first step of producing an equivalent circuit that does not include a signal transmission path corresponding to a false path, based on circuit information indicating connection between components in the integrated circuit; and a second step of evaluating the integrated circuit by using the equivalent circuit produced in the first step.
According to the present invention, evaluation can be conducted by using the equivalent circuit including no false path, allowing for rapid, accurate evaluation of performance of the integrated circuit.
Preferably, in the circuit evaluation method according to the present invention, false path information indicating the false path is used, and the false path information represents the false path by two vertices on a graph representing the integrated circuit.
Preferably, the first step includes the steps of extracting a first partial circuit provided with a first vertex as an input and a second vertex as an output, the first vertex and the second vertex being two vertices representing the false path, making a copy of the first partial circuit as a second partial circuit, and modifying connection of the first and second partial circuits and another circuit such that there exists no path from the first vertex toward the second vertex.
According to the present invention, in a method for extracting a false path in an integrated circuit to be designed, the false path is extracted using an activating condition of a non-control signal edge within each logic gate included in the integrated circuit.
Preferably, the false path extraction method according to the present invention includes the steps of: propagating a logic value listed in the activating condition of a non-control signal edge within a first gate by a propagation process; conducting repeatedly the propagation step while the value to be propagated is a control signal; and detecting a path from the first gate to a second gate as the false path when the propagated value is inconsistent with the activating condition of a non-control signal edge within the second gate.